package main.adt.list;

import java.util.Arrays;

/**
 * Created by july on 2015/12/10.
 * 线性表的顺序存储---顺序表
 * 基本操作：
 *  1、初始化一个空的顺序表
 *  2、建立一个指定容量的空顺序表
 *
 *  3、添加数据到顺序表尾
 *  4、添加数据到顺序表指定位置
 *
 *  5、移除顺序表尾部数据
 *  6、移除顺序表指定位置的数据
 *  7、清空顺序表
 *
 *  8、修改顺序表指定位置的数据
 *
 *  9、随机访问顺序表中的数据
 *  10、查询指定数据在顺序表中首次出现的位置
 *
 *  11、获取顺序表中元素个数
 *  12、判断顺序表是否为空
 *
 */
public class SequenceList<E> {

    private static final int DEFAULT_CAPACITY = 8;  //默认初始容量

    private int capacity;                           //当前容量
    private int size;                               //当前元素个数
    private Object[] data;                          //数据

    public SequenceList(){
        this(DEFAULT_CAPACITY);
    }

    public SequenceList(int capacity){
        if(capacity <= 0){
            throw new IllegalArgumentException("初始集合时capacity参数值不能小于0");
        }
        this.data = new Object[capacity];
        this.capacity = capacity;
    }

    /**
     * 将数据追加到表尾
     * 确定数组容量后，添加数据到表尾,元素个数加1
     * @param element
     * @return
     */
    public boolean add(E element){
        ensureCapacity(size + 1);
        data[size++] = element;
        return true;
    }

    /**
     * 在集合的指定位置插入数据,插入数据时，指定位置后的数据需要依次后移以空出位置插入新数据
     * 移动从顺序表尾开始向前移动直到index处，index位置空出来好插入数据
     * 如果等于0表示在表头插入数据，那么集合中的所有元素都需要后移,时间复杂度O(n).
     * 如果等于size,表示在表尾追加数据，集合中的所有元素不需要移动，时间复杂度O(1).
     * @param index
     * @param element
     * @return
     */
    public boolean add(int index,E element){
        checkAddIndex(index);
        ensureCapacity(size + 1);
        int moveNum = size - index;
        if(moveNum > 0){
            System.arraycopy(data,index,data,index + 1,moveNum);
        }
        data[index] = element;
        size++;
        return true;
    }

    /**
     * 从表尾移除数据。
     * 直接定位到表尾数据然后删除，不涉及到移动数据
     * @return
     */
    @SuppressWarnings("unchecked")
    public E remove(){
        E oldEle = (E) data[size - 1];
        data[--size] = null; //一定要加上这句，防止内存泄漏
        return oldEle;
    }

    /**
     * 从指定位置处移除数据
     * 删除时，需要将指定索引处后面的数据以此向前平移，然后释放掉指定位置的空间时间复杂度和插入数据一样
     * 所以说在插入和删除比较频繁的时候应该选择用链表结构，而不应该用顺序结构
     * @param index
     * @return
     */
    @SuppressWarnings("unchecked")
    public E removeByIndex(int index){
        checkIndex(index);
        E oldEle = (E) data[index];
        int moveNum = size - index - 1;
        if(moveNum > 0){
            System.arraycopy(data,index + 1,data,index,moveNum);
        }
        data[--size] = null;
        return oldEle;
    }

    /**
     * 清空顺序表
     */
    public void clear(){
        Arrays.fill(data, null);
        size = 0;
    }

    /**
     * 修改顺序表指定位置的数据
     * @param index
     * @param element
     * @return
     */
    public boolean set(int index,E element){
        checkIndex(index);
        data[index] = element;
        return true;
    }

    /**
     * 查询指定位置的元素
     * @param index
     * @return
     */
    @SuppressWarnings("unchecked")
    public E get(int index){
        checkIndex(index);
        return (E) data[index];
    }

    /**
     * 查询指定数据在顺序表中首次出现的位置，如果不存在返回-1
     * @param element
     * @return
     */
    public int indexOf(E element){
        for(int i = 0; i < size; i++){
            if(element == null){
                if(data[i] == null){
                    return i;
                }
            }else{
                if(element.equals(data[i])){
                    return i;
                }
            }
        }
        return -1;
    }

    /**
     * 判断集合是否为空
     * @return true:空；false：不为空
     */
    public boolean isEmpty(){
        return size == 0;
    }

    /**
     * 获取集合中元素个数
     * @return
     */
    public int size(){
        return size;
    }

    /**
     *  复写toString方法，便于查看集合中的数据
     */
    @Override
    public String toString() {
        if(size == 0){
            return "[]";
        }
        StringBuilder sb = new StringBuilder("[");
        Object temp;
        for(int i = 0;i < size;i++){
            temp = data[i];
            if(temp != null){
                sb.append(temp.toString()).append(',');
            }else{
                sb.append("Null").append(',');
            }
        }
        int len = sb.length();
        sb.delete(len-1,len).append("]");
        return sb.toString();
    }

    /**
     * 由于盛装数据的数组容器的容量是固定的，所以在每次插入新数据之前要先检查集合的容量是否
     * 能容纳新添加的数据元素。
     * 判断方法：
     *  如果集合中的元素已经达最大值,直接抛出异常（如果size=Integer.MAX_VALUE,那么size+1会小于0）
     *  如果所需容量大于当前容量，就将集合容量增加1.5倍，增加后判断容量是否溢出，如果增加后的容量减去
     *  所需容量小于0就说明增加后的容量溢出了，此时就将所需容量作为增加后的容量。
     *  容量增加后就将集合中的数据复制到新数组里。
     * @param minCapacity
     */
    private void ensureCapacity(int minCapacity) {
        if(minCapacity <= 0){
            throw new IllegalArgumentException("当前集合容量已达最大值，无法继续增加容量");
        }
        if(minCapacity > capacity){
            while(capacity < minCapacity){
                capacity = capacity + capacity >> 1;
            }
            if(capacity - minCapacity < 0){
                capacity = minCapacity;
            }
            data = Arrays.copyOf(data,capacity);
        }
    }

    /**
     * 检查插入位置，插入位置不能小于0且不能大于集合中的元素个数
     * @param index
     */
    private void checkAddIndex(int index){
        if(index < 0 || index > size){
            throw new IndexOutOfBoundsException("插入位置有误，当前集合元素个数为：" + size +" 插入位置却为：" + index +" 明显不对嘛");
        }
    }

    /**
     *检查查询位置
     * @param index
     */
    private void checkIndex(int index){
        if(index < 0 || index > size - 1){
            throw new IndexOutOfBoundsException("指定索引位置有误");
        }
    }

}
